package 链表题.判断回文链表;

/**
 * 步骤一: 找到中间点
 * 步骤二: 中间点后半个链表反转
 * 步骤三: 反转后链表与原链表注意比较
 */

import 链表题.ListNode;

// 1. 找得到中间值
public class Test1 {
    public static ListNode middleNode(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

    // 2. 反转后半个链表
    private static ListNode reverse(ListNode o1) {
        ListNode n1 = null;
        while (o1 != null) {
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        return n1;
    }

    public static boolean isPalindrome(ListNode head) {
        // 比较倒转的链表和原来的链表(倒转的链表为该一半(偶数取右边元素), 一定比原来链表元素少, 故只要比完倒转元素就可以断言为回文链表)
        ListNode middle = middleNode(head);
        ListNode newMiddle = reverse(middle);
        while (newMiddle != null) {
            if (head.val != newMiddle.val) {
                return false;
            }
            newMiddle = newMiddle.next;
            head = head.next;
        }
        return true;
    }


    public static void main(String[] args) {
        ListNode n = ListNode.of(1, 2, 3, 2, 1);
        ListNode n1 = ListNode.of(1, 6, 8, 4, 4, 8, 6, 1);
        ListNode n2 = ListNode.of(1, 6, 8, 4, 6, 1);
        System.out.println(isPalindrome(n));
        System.out.println(isPalindrome(n1));
        System.out.println(isPalindrome(n2));
    }
}
